Spurred by recent advances in machine recognition systems, machine-readable markers (e.g. one and two-dimensional barcodes) are being increasingly incorporated in media used to convey information for recognition by both humans and machines. For example, one-dimensional barcodes have been incorporated on labels applied to merchandise articles, which labels can be both read by humans and scanned by machines, with operator assistance, as at supermarket checkout counters. Both one and two dimensional barcodes have been incorporated on human-readable media, such as airway bills and facsimile order sheets which can be automatically scanned to facilitate communication of information to both humans and machines handling the media.
A number of patents describe systems which locate one or two-dimensional barcodes by searching for predetermined position marks placed in the vicinity of the barcodes. For example, U.S. Pat. Nos. 4,736,109 and 5,241,166 describe systems in which concentric ring markings are placed close to the area of encoded information to facilitate locating a two-dimensional barcode from within an image.
Other patents describe systems which analyze an image to locate a predetermined "finder" pattern which appears in a barcode (U.S. Pat. No. 5,189,292), or to locate predetermined "start and stop" patterns of a barcode (U.S. Pat. No. 5,304,787). Another system described in U.S. Pat. No. 5,262,623 locates a one-dimensional barcode by searching for a predetermined two-dimensional marking within an image.
Other prior art references describe systems which locate one-dimensional barcodes by locating portions of an image which exhibit one or more properties of the barcode. For example, U.S. Pat. No. 4,988,852 describes a system which locates one-dimensional barcodes by counting pixel transitions within different portions of an image and comparing the counts thus obtained to a predetermined count value which is characteristic of known barcodes. Another system described in U.S. Pat. No. 5,073,954 locates one-dimensional barcodes by creating and analyzing horizontal and vertical histograms of the image.
The Article "Bar Code Localization Using Texture Analysis," authored by Jain et al. and published in Proceedings of the Second International Conference on Document Analysis and Recognition in October, 1993 describes a method of locating one-dimensional barcodes through multiple channel Gabor filtering of the image. Based on such filtering, one or more portions of the image which exhibit high "radial" frequencies at given angles are identified as containing a one-dimensional barcode.
The Article "Bar Code Location Algorithm Using a Two-Dimensional Approach" authored by Viard-Gaudin, also published in Proceedings of the Second International Conference on Document Analysis and Recognition in October, 1993 describes a system which locates one-dimensional barcodes by determining a "density of mono-oriented gradient", i.e. by analyzing the rate at which changes in pixel polarity occur along given directions within the image. Portions of the image where such density is highest are determined to contain a one-dimensional barcode.
While existing systems are described as being capable of locating one-dimensional barcodes by matching image characteristics to properties of the one-dimensional barcode, no such system has heretofore been known for locating two-dimensional barcodes.
Accordingly, it is an object of the present invention to provide a method of locating a two-dimensional machine-readable marker containing encoded information from within an image, without requiring special locator markings to be placed in the vicinity of the marker.
A further object of the invention is to perform morphological operations and a statistical analysis to locate a machine-readable marker having predetermined size, shape and pixel distribution (i.e. texture) characteristics.
Still another object of the invention is to provide a method of locating a two-dimensional marker which has a random and homogeneous distribution of cells of first and second (e.g. black and white) pixel polarities.
A further object of the invention is to provide a method of locating a two-dimensional machine-readable marker which does not require a computationally intensive manipulation of a pixel distribution over an entire image.